COMMENT ⊗   VALID 00012 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	.s(WRITIN, WRITING RECURSIVE FUNCTION DEFINITIONS)
C00006 00003	.ss(tdvsbu,Static and dynamic ways of programming.)
C00012 00004	.ss(numrec,Recursive definition of functions on natural numbers.)
C00022 00005	.ss(listrec,Simple list recursion.)
C00032 00006	.ss(sexprec,Simple S-expression recursion.)
C00039 00007	.if false then begin "sack"
C00040 00008	.ss(strucrec,Other structural recursions.)
C00044 00009	.<<ex: bool exp ::= 0 | 1 | and | or | not  write evaluator >>
C00045 00010	.ss(treerec,General tree recursion.)
C00053 00011	.ss(soln, Solving a LISP programming problem.)
C00069 00012	.ss(writinex, Lots of LISP functions to program.)
C00095 ENDMK
C⊗;
.s(WRITIN, WRITING RECURSIVE FUNCTION DEFINITIONS)
.if NOTASSEMBLING then start
.PROVIN: NEXT SECTION!;
.PROVEX: NEXT SECTION!;
.IMPURE: NEXT SECTION!;
.MACHIN: NEXT SECTION!;
.SEARCH: NEXT SECTION!;
.EXTEND: NEXT SECTION!;
.ABSNTX: NEXT SECTION!;
.COMPIL: NEXT SECTION!;
.COMPUT: NEXT SECTION!;
.end


	In the Chapter {SECTION READIN} we discussed the basic constructs of 
LISP and explained how to evaluate terms built up using these constructs.  
The notion of recursively defined function was introduced and the rules for 
computing the value of a recursively defined function were given.  
In addition we showed how LISP programs are represented as S-expressions and 
how these programs are interpretered by the function ⊗eval.   
By now you should be able to read and understand simple LISP programs.  
The next step is learning
to write LISP programs.  In principle you already know all that is necessary,
however there are some basic ideas and  techniques which are 
useful in solving LISP programming problems.  The purpose of
this chapter is to help you learn to think recursively and to familiarize
you with some of the basic techniques and
standard forms of recursive programs.  The final section contains 
a collection of
problems of varying degrees difficulty for you practice on.

.ss(tdvsbu,Static and dynamic ways of programming.)

	In order to write recursive function definitions, one must
think about programming differently than is customary when writing
programs in languages like FORTRAN or ALGOL or in machine language.
In these languages, one has in mind the state of the computation as
represented by the values of certain variables or locations in the
memory of the machine, and then one writes statements or machine
instructions in order to make the state change in an appropriate way.
When writing recursive function definitions one takes a different approach.
Namely, one thinks about the value of the function, asks for what
values of the arguments the value of the function is immediate, and,
given arbitrary values of the arguments, for what simpler
arguments must the function be known in order to give the value of
the function for the given arguments.  

	Let us consider a numerical
example; namely, suppose we want to compute the function ⊗n!.  For
what argument is the value of the function immediate.  Clearly, for
⊗n = 0 or ⊗n = 1, the value is immediately seen to be 1.  Moreover,
we can get the value for an arbitrary ⊗n if we know the value for
⊗⊗n-1⊗.  Also, we see that knowing the value for ⊗n = 1 is redundant,
since it can be obtained from the ⊗n = 0 case by the same rule as
gets it for a general ⊗n from the value for ⊗⊗n-1⊗.  All this talk
leads to the simple recursive definition:

!fcnfact&1  ⊗⊗⊗n! ← qif n=$0 qthen $1 qelse nq*[n-$$1$]!⊗.

	We may regard this as a static way of looking at programming.
We ask what simpler cases the general case of our function depends on
rather than how we build up the desired state of the computation.

	An example of the dynamic approach to programming is
the following obvious ALGOL 60 program for computing ⊗n!:  
.begin nofill select 2 turnon "∂" group
.n←20

∂(n+5)			    %3integer procedure%* factorial(n); %3integer%* s,i;
∂(n)		    %3begin%*
∂(n+5)			    s := $$1$;
∂(n+5)			    i := ⊗⊗n⊗;
∂(n)loop: 	      ∂(n+5)qif i = $0 qthen qgo done;
!fcnfactorial& ∂(n+5)			    s := i*s;
∂(n+5)			    i := i-$$1$;
∂(n+5)			    qgo loop;
∂(n)done:            ∂(n+5) factorial := s;
∂(n)		    %3end%*;

.end

	One often is led to believe that static = bad and  dynamic = good,
but in this (particularly favorable) case the LISP program is shorter and clearer.
In general this style of thinking and programming can produce clean simple
programs.  It also provides a built in mechanism of problem solving
which is rather like what is usually called ⊗subgoaling.  We shall also
see later how this style leads to rather natural methods of proving statements
about programs.

	 Actually, when we discuss the mechanism of
recursion, it will turn out that the LISP program is inefficient
because it uses
the pushdown mechanism unnecessarily and should be replaced
by the following somewhat longer program that corresponds to the
above ALGOL program rather precisely:
.begin nofill

⊗⊗⊗        n! ← fact[n,$$1$],		               ⊗
!fcnfact&2 
⊗⊗⊗fact[i, s] ← qif i=$0 qthen s qelse fact[i-$$1$, iq*s]⊗.
.end

	Perhaps the distinction between the two styles
is equivalent to what some people call
the distinction between ⊗top-down and ⊗bottom-up programming
with ⊗static corresponding to ⊗top-down.  
LISP offers both, but the static style is better developed in LISP,
and we will emphasize it.
.ss(numrec,Recursive definition of functions on natural numbers.)

	In the next several sections we examine various forms of recursive
function definition and programs having such forms.
We begin by considering recursive definitions of numerical functions.
We have already seen one example, namely the factorial function.
The basic idea is to give a rule for computing the value of the function
for a particular value of the argument (input)
in terms of some collection of given (defined or built in) functions and values of 
the function for smaller arguments.   Notice that we will have to
specify the value for $0 directly as there are no smaller numbers.
The method of function definition is parallel to the description of the
domain of natural numbers in terms of the number $0 and the operation 
of successor, namely a number is either $0 or obtained 
by applying successor to a previously constructed number.

	Recursive functions of natural numbers have the the subject of much study
by logicians and mathematicians.  One fairly nice result is that any
such function can be computed starting with the constant $0, the
basic functions ⊗add1 (more commonly known as ⊗successor) ⊗sub1 (also known 
as ⊗predecessor) and the tools
for recursive definition described in Chapter {SECTION READIN}.
(Actually one can get by with less, but that is not the point of this discussion.)  
For example the sum and difference of two numbers are given by

!fcnplus& ⊗⊗⊗plus[n,m] ← qif n=$0 qthen m qelse plus[n-$$1$,m]+$$1$⊗

!fcndiffer& ⊗⊗⊗differ[n,m] ← qif n=$0 qthen $0 qelse qif m=$0 qthen n qelse differ[n-$$1$,m-$$1$]⊗

while the predicate ⊗greaterp which is true if the first argument is
greater that the second can be computed by

!fcngreaterp& ⊗⊗⊗greaterp[n,m] ← qif n = $0 qthen $0 qelse qif m = $0 qthen $1 qelse 
greaterp[n-$$1$,m-$$1$]⊗

Here we use $0 to represent qfalse and $1 to represent qtrue in order to
keep within the domain of numbers.  We also write ⊗⊗n+$$1$⊗ instead of ⊗⊗add1 n⊗
and ⊗⊗n-$$1$⊗ instead of ⊗⊗sub1 n⊗.

	We could continue along these lines using ⊗plus to define ⊗times, 
⊗times to define ⊗exp, ⊗differ to define ⊗quot and ⊗rem, and so forth
building up a collection of useful functions.  We will leave this as an exercise
for the reader.  The point is that at each stage the recursive definition
is expressed in terms of given functions in a very simple form.
Perhaps the simplest such form is the following schema:

!eqnpr1 ⊗⊗⊗f[n] ← qif n=$0 qthen $a qelse h[n-$$1$,f[n-$$1$]]⊗.

Here ⊗f is defined in terms of a fixed constant $a and a given function ⊗h. 
This corresponds to "primitive recursion" without parameters.  If we
take  ⊗⊗h[k,m]=[k+$$1$] q* m⊗ and $a = $1 we have the definition of ⊗fact 
given above {eqn fact1}.

If we allow parameters to be carried along we get the usual form of
primitive recursion (shown with only one parameter for simplicity)

!eqnpr2 ⊗⊗⊗f[n,m] ← qif n=$0 qthen g[m] qelse h[n-$$1$,m,f[n-$$1$,m]]⊗

The definition of ⊗plus given above has this form with ⊗g[m]=m and
⊗⊗h[n,m,k]=k+$$1$⊗.   As a further generalization we allow the 
parametric argument of ⊗f (in the recursive call)
to be a given function of the parameter and the first argument giving

!eqnpr3 ⊗⊗⊗f[n,m] ← qif n=$0 qthen g[m] qelse h[n-$$1$,m,f[n-$$1$,j[n-$$1$,m]]]⊗.

The definitions of ⊗differ and ⊗greaterp given above has this form.  Also the 
alternate recursive definition of the factorial function {eqn fact2} 
is of this form.
We may wish to express the computation directly in terms of several
preceding values instead of just ⊗⊗f[n-$$1$]⊗.   One form of this
"course of values" type recursion is given by
.begin nofill turnon "∂"
.n←24

∂(n)⊗⊗f[n] ← qif n=$0 qthen $$a$%40%* qelse⊗
∂(n)⊗⊗	 qif n=$1 qthen $$a$%41%* qelse⊗
!eqnpr4 ∂(n+8)      ..........

∂(n)⊗⊗	 qif n=$b qthen $$a$%4b%* qelse⊗
∂(n)⊗⊗	   h[n,f[p%41%*[n]],...f[[p%4c%*[n]]]⊗
.end
 where ⊗⊗$$0$≤p%4i%*[n]<n⊗ for $1≤i≤k when ⊗⊗$$b$<n⊗.  As an example we have the
definition of the function giving the ⊗⊗n⊗th Fibonacci number:

!fcnfib& ⊗⊗⊗fib[n] ← qif n=$0 qthen $0 qelse qif n=$1 qthen $1 qelse fib[n-$$1$] + fib[n-$$2$]⊗

We note that this is a particularly unfavorable case for recursively defined 
functions as the evaluation from this definition takes order of ⊗fib_n amount of 
work for input of ⊗n.  A more efficient definition is:
.begin nofill

⊗⊗⊗fiba[n] ← fibb[n,$$0$,$$1$]                 ⊗
!fcnfib&a 
⊗⊗⊗fibb[n,k,m] ← qif n=$0 qthen k qelse fibb[n-$$1$,m,m+k]⊗
.end
Evaluation of the ⊗⊗n⊗th Fibonacci number using this definition requires
only order of ⊗n amount of work.

	The above forms of recursive function definition all have a very nice 
property.  Namely, assuming that the given functions appearing in the schemas 
are total, the function defined by the schema is total.  That is the rules given for
evaluation of such functions will always produce an answer in a finite number of
steps.  The general form of recursive definition

!eqnprec ⊗⊗⊗f[n1,...,nk] ← qt[f,n1,...,nk]⊗

where qt is some term involving ⊗f, the arguments ⊗ni and perhaps additional
given functions.   Definitions of this general form are not guaranteed to
define total functions.   For example

!fcnloop& ⊗⊗⊗loop n ← loop n⊗

is a perfectly good definition, however the rules for computation will
not produce an answer for any value of ⊗n.  There are of course many cases
where the function defined by a recursive definition is total, but where
the definition does not fit any of the above patterns.  

	The standard example of a total function on natural numbers that
is not definable by primitive recursion is known as Ackerman's function and
is defined by

!fcnack& ⊗⊗⊗   ack[m,n] ← qif m=$0 qthen n+$1 qelse qif n=$0 qthen ack[m-$$1$,$$1$]
qelse ack[m-$$1$,ack[m,n-$$1$]]⊗.

If you work out the values of ⊗⊗ack[m,n]⊗ for increasing values of the arguments,
you will see that the amount of computation grows very rapidly.   This
is related to the fact that the function can not be defined by any 
collection of primitive recursion schemas.
.ss(listrec,Simple list recursion.)

	About the simplest form of recursion in LISP occurs when one
of the arguments is a list, the result is immediate when the argument
is null, and otherwise we need only know the result for the d-part of
that argument.  Several of the functions defined in Chapter {SECTION READIN}
are of this form.
Consider, for example, ⊗⊗u*v⊗, the result of ⊗⊗append⊗ing
the list ⊗v to the list ⊗u. 
The result is immediate for the case qn ⊗u and
otherwise depends on the result for qd ⊗u.  Thus, we have

!fcnappend&1 ⊗⊗⊗u*v ← qif qn u qthen v qelse qa u . [qd u * v]⊗.

Notice that if we had tried to recur on ⊗v rather than on ⊗u 
we would not have been successful.  The result would be immediate for
qn ⊗v, but ⊗⊗u*v⊗ cannot be constructed in any direct way from ⊗⊗u*qd v⊗
without a function that puts an element onto the end of a list.
(From a strictly list point of view, such a function would be as
elementary as ⊗cons which puts an element onto the front of a list,
but, when we consider the implementation of lists by list structures,
we see that the function is not so elementary.  This has led some
people to construct systems in which lists are bi-directional, but,
in the main, this has turned out to be a bad idea).  Anyway, it is
usually easier to recur on one argument of a function than to recur
on the others.  

Another example is the function ⊗member that tests for membership in
a list.  If the list is empty then the answer is qNIL otherwise
either the element we are searching for is the first thing on the
list, or it is in the rest of the list.  This reasoning gives rise
to the recursive definition

!fcnmember&1 ⊗⊗⊗member[x,u] ← qif qn u qthen qNIL qelse x = qa u ∨ member[x,qd u]⊗.

The reader should observe that this definition is equivalent
to that given by ({eqn member!!}) using only logical connectives.

	The function ⊗reverse is another example of simple list recursion.

!fcnreverse&1 ⊗⊗⊗reverse[u] ← qif qn u qthen qNIL qelse [reverse qd u] * [qa u . qNIL]⊗

This straight forward definition of ⊗reverse  involves ⊗⊗append⊗ing
the ⊗reverse of the rest of the list to the list containing only
the first element of the list.  

	As with recursive definition of numerical functions we see that
simple list recursion parallels the description of the domain of lists
which says that a list is either qNIL or it is the result of ⊗⊗cons⊗ing an 
S-expression onto a "smaller" list.   
We can give recursion schemas for list recursion analagous to
those for numerical functions.   
In general, the recursive definition of a function on lists must
take into account the fact that we have not one "successor" of a given
list, but one for each possible S-expression.
For example "primitive list recursion" without parameters has the form

!eqnlpr1 ⊗⊗⊗f[u] ← qif qn u qthen g0 qelse h[qa u, qd u, f[qd u]]⊗

Taking g0 = qNIL and ⊗⊗h[x,v,w]= w * [x . qNIL]⊗ we get the definition
of ⊗reverse given above {eqn reverse1}.
If we mix numerical and list computation  taking g0=$0 and ⊗⊗h[x,u,n]=n+$$1$⊗
we get

!fcnlength&h1 ⊗⊗⊗length[u] ← qif qn u qthen $0 qelse length[qd u]+$$1$⊗

The function ⊗last  which computes the last element of a list is another example.  

!fcnlast&1 ⊗⊗⊗last u ← qif qn qd u qthen qa u qelse last qd u⊗,


In order to fit the schema exactly the above definition needs to be patched
somewhat.  See if you can figure out what must be done and what
the "given" function ⊗h should be.  

The schema for primitive list recursion with parameters (only one parameter shown)
is

!eqnlpr2 ⊗⊗⊗f[u,x] ← qif qn u qthen g[x] qelse  h[qa u, qd u, x, f[qd u, v]]⊗.

⊗append {eqn append1}, ⊗member {eqn member1} and ⊗assoc ({eqn assoc!!})
are examples of this form of definition.   
Allowing a given function of the arguments to occur in the parameter position
in the recursive call on ⊗f we obtain the schema

!eqnlpr3 ⊗⊗⊗f[u,x] ← qif qn u qthen g[x] qelse h[qa u, qd u, x, f[qd u, j[qa u, qd u, x]]]⊗.

The definition of ⊗reverse ({eqn reversea!!}) in terms of the basic ⊗cons operation, 
itself and an auxiliary variable has this form.

	The simple recursion on lists without parameters simply proceeds through
a list gathering results to be used in constructing the answer, but provides no
access to information previously obtained.  When we allow parameters to be
carried along the information can be passed down the list as well as results
being passed back up.  The appropriate mixing of control structure and
information passing is often the key to solving a programming problem.
We shall see in a later sections how one can sometimes solve the two
aspects of the problem separately and then piece together the results.

	The function ⊗alt ({eqn alt!!}) which returns a list of alternate
elements of a list is also based on list recursion, however the form of the
recursion is different.
Here the base
cases are the empty list and the list containing one element.  In the
general case we use the result for qdd ⊗u to compute the result for ⊗u.  
This is analogous to the "course of values" recursion on numbers {eqn pr4}.

	The above schemas, like their numerical counterparts yield definitions
of total functions (assuming that the given functions are total).
The most general form of list recursion is the same as that for numerical
recursion {eqn prec}.  In the case of pure list recursion we build the term on the
right hand side from basic list functions and expect the arguments to be lists.
As we have seen above we often mix computation involving lists, numbers and
S-expression in general.
Also, as with numerical recursion, recursive definition of functions
on lists does not in general give rise to total functions and some
care must be used to make sure your program will terminate.   We will
have more to say about proving termination in Chapter {SECTION PROVIN}.

.ss(sexprec,Simple S-expression recursion.)

	In the case of recursion on the structure of S-expressions,
the simplest situation is when the value of the function is
immediate for atoms, and for non-atoms depends only on the
values for the a-part and the d-part of the argument.  Thus ⊗subst 
was defined by

!fcnsubst&1 ⊗⊗⊗subst[x,y,z] ← qif qat z qthen [qif z qeq y qthen x qelse z]
qelse subst[x,y,qa z] . subst[x,y,qd z]⊗.

More generally we have recursive definitions of the form

!eqnspr1 ⊗⊗⊗f[x] ← qif qat x qthen g[x] qelse h[qa x, qd x, f[qa x], f[qd x]]⊗.

Here again the recursive definition of functions parallels the description
of the domain. 
The definitions of ⊗size (the number of atoms in an S-expression) and ⊗fringe 

!fcnsize&1 ⊗⊗⊗size[x] ← qif qat x qthen 1 qelse size qa x + size qd x⊗

!fcnfringe&1 ⊗⊗⊗fringe x ← qif qat x qthen <x> qelse fringe qa x * fringe qd x⊗

are further examples of this form of definition.

	The S-expression analogue of {eqn pr3} and {eqn lpr3} 
(primitive S-expression recursion) is 

!eqnspr3 ⊗⊗⊗f[x,y] ← qif qat x qthen g[x,y] qelse h[qa x,qd x,y,f[qa x,ja[x,y]],f[qd x,jd[x,y]]]⊗

and the following definition of ⊗equal is of this form

!fcnequal&1 ⊗⊗⊗   x=y ← qif qat x qthen [qif qat y qthen x qeq y qelse qNIL] qelse 
qif qat y qthen qNIL qelse qa x=qa y ∧ qd x=qd y⊗.

Note that using the fact that qeq is in fact defined on non-atoms in
actual LISP implementations and properties of the propositional functions,
we can simplify the definition of ⊗equal to 

!fcnequal&2 ⊗⊗⊗x = y ← x qeq y ∨ [¬qat x ∧ ¬qat y ∧ qa x = qa y ∧ qd x = qd y]⊗.

as was given in Chapter {SECTION READIN}.

	Although the above definition of ⊗equal is an instance of the schema
{eqn spr3} it is more natural to think of it as a parallel recursion through
the two arguments rather than thinking of one of them as a parameter.  This
could of course be elaborated to carry along parameters as well as recurring
in parallel through some collection of arguments. 
In later chapters we will see more examples of programs that recur on more
than one argument.  (For example ⊗samefringe ({eqn samefringe!!}).
The important point to check in such programs is that the collection 
of arguments being recurred on is always "simpler" in recursive calls
to the program being defined.

	The definition of ⊗flatten is an example of a double recursion.
.begin nofill

⊗⊗⊗flatten[x] ← flat[x, qNIL]		⊗
!fcnflatten&2  
⊗⊗⊗flat[x,y] ← qif qat x qthen x . y qelse flat[qa x,flat[qd x,y]]⊗
.end
Although ⊗flatten computes the same function as ⊗fringe, it
is more efficient  because the ⊗append operation used by ⊗fringe 
copies unnecessarily.   As we shall see in Chapter {SECTION CONTRO},
⊗flatten is also an improvement over ⊗fringe in that it is partially 
amenable to tail recursive evaluation.   
The kind of double recursion used in ⊗flatten is often useful. 
One way of thinking of this form of recursion is that results are
computed from one side of the S-expression (the qqd side in this case) and then
passed along to the other side.  Thus we obtain a flow of information
from side to side as well as top to bottom.
The technique of writing a simple and easily understandable recursive definition
and then later optimizing by the kind of transformation made in going from
⊗fringe to ⊗flatten is often useful.  

	Note that the definition of ⊗flat does not fit the general
primitive recursive schema {eqn spr3}. 
Thus we have an example where one definition of a function clearly fits 
one of the simple recursion schemas and thus defines a total function, while
for another definition of the function this fact is not immediate.  Of
course showing that both definitions compute the same function also requires
some work.   We could add to our list of schemas some which
allow multiple recursions such as exhibited by ⊗flatten.  
However no matter how many such forms for defining total functions we allow,
we will eventually have to resort to the general form {eqn prec} which
is also the general form for S-expression recursion.
.if false then begin "sack"

	As a curiosity consider the following definition

⊗⊗⊗sack[x,y] ← qif qat x qthen x . y qelse qif qat y qthen sack[qa x, qd x] 
qelse sack[qd x, sack[x , qd y]]⊗.

This is an S-expression analogue to the function ⊗ack defined in 
section qsect{subsection numrec} 
on numerical recursion.  Unlike ⊗flat the occurrence of double recursion
(⊗⊗sack[...,sack[...]]⊗) is crucial.  Like ⊗ack this function cannot
be defined by any collection of simple recursive schemata.

.end "sack"
.ss(strucrec,Other structural recursions.)

	When S-expressions are used to represent a class of
expressions that are defined inductively then functions of these
expressions often have a recursive form closely related to the 
inductive definition of the expressions.  For example the
arithmetic interpreter ⊗numval ({eqn numval!!}) computes directly
the value for constants and variables and for sums and products
it computes the value in terms of the values 
of the subexpressions from which the sum or product is constructd.  
The function ⊗diff ({eqn diff!!}) which symbolically
differentiates the same class of expressions has a similar recursive
structure in that it knows the answers immediately for constants
and variables and for sums and products it uses the results for
subexpressions to obtain the final answer.  If we consider the arithmetic
expressions where sum and product are simple binary operators we can
write a simple recursion schema as follows:

.begin nofill group turnon "∂"
.n←12; m←16

∂(n)⊗⊗f[x,y] ←⊗ 
	 ∂(m)⊗⊗qif num[x] qthen gnum[x,y] qelse⊗
!eqngpr1 ∂(m)⊗⊗qif isvar[x] qthen gvar[x,y] qelse⊗
	 ∂(m)⊗⊗qif issum[x] qthen gsum[s1 x, s2 x, y, f[s1 x, y], f[s2 x, y]] ⊗
	 ∂(m)⊗⊗qelse qif ispro[x] qthen gprod[p1 x, p2 x, y, f[p1 x, y], f[p2 x, y]]⊗
.end
Then the evaluation function ⊗numval 
.begin nofill group turnon "∂"
.n←12; m←16

∂(n)⊗⊗numval[x,y] ←⊗
	∂(m)⊗⊗qif isnum[x] qthen cval[x] qelse⊗
!fcnnumval&1 ∂(m)⊗⊗qif isvar[x] qthen lookup[x,y] qelse⊗
	∂(m)⊗⊗qif issum[x] qthen sum[numval[s1 x,y] numval[s2 x,y]] ⊗
	∂(m)⊗⊗qelse qif isprod[x] qthen prod[numval[p1 x,y] numval[p2 x,y]] ⊗
.end
is an instance of this schema where ⊗cval, ⊗lookup, ⊗sum and ⊗prod are given.

	A more complicated example of
an interpreter with recursive structure based on the expression
language structure is the LISP interpreter ⊗eval ({eqn evall!!}).

	In general if we have a domain defined by starting with
a base set (with computable test for membership) and a collection
constructors with which we build elements of the domain by
repeated application starting with elements of the base set,
then there is a corresponding schema for recursive definition of 
functions on this domain.   We will see more examples and have 
more to say about this in later chapters.

.<<ex: bool exp ::= 0 | 1 | and | or | not  write evaluator >>
.ss(treerec,General tree recursion.)

	A tree structure is either a leaf or a node together with
a collection of immediate successors which are also trees.  Many data structures
can be viewed as trees.  For example, S-expressions with leaves being atoms 
and each non-leaf tree has two successors, given by the ⊗car and the ⊗cdr.  
More generally the structures described in section qsect{subsection strucrec}
can be thought of as tree like structures with the basic elements as leaves,
and each non-leaf tree having immediate successors given by the selector
functions for the particular type of node.  These structures all have two things
in common.  Namely, (i) each kind of node has a fixed number of successors and
(ii) when doing computations each such tree, is constructed from parts already
present.  

	A another example is a tree  which is given by an initial position
together with a ⊗successors function from which we may obtain the immediate
successors of any position (of relevance).  Here a node may have an arbitrary
number of successors and parts of the trees are built as needed.
Functions on such trees typically involve two processes, one for recognizing
and dealing with leaves and one for processing a collection of succesors.
(Of course the two processes interact recursively.)  

	Consider the problem for searching a tree for a position having some
particular property.   We can write a program that describes a depth
first  search independent of the property or kind of tree.
It can be used to search specific trees  by defining the
three auxiliary functions ⊗successors, ⊗ter, and ⊗lose for the particular
problem.  We have
.begin turnoff "{}" group

!fcnsearch&d   ⊗⊗⊗search p ← qif lose p qthen $LOSE qelse qif ter p qthen p qelse searchlis[successors p]⊗

where

!fcnsearchlis&d  ⊗⊗⊗searchlis u ← qif qn u qthen $LOSE qelse
[λx: qif x = $LOSE qthen searchlis qd u qelse x][search qa u]⊗.
.end

In the applications, we start with a position ⊗p0, and we
are looking for a win in the successor tree of ⊗p0.  Certain
positions lose and there is no point looking at their successors.
This is decided by the predicate ⊗lose.  A position is a win if
it doesn't lose and it satisfies the predicate ⊗ter.  The
successors of a position are given by the function ⊗successors, 
and the value of ⊗⊗search p⊗ is the winning position.  No
non-losing position should have the name $LOSE or the function won't
work properly.

	One application is finding a path from an initial node to
a final node in a graph represented by a list structure as described
in chapter I.  A position is a path starting from the initial node
and continuing to some intermediate node and is represented by a
list of its nodes in reverse order.  The three functions for this
application are
.begin nofill group turnon "∂"
.n←20

!fcnlose&path  ∂(n)⊗⊗lose p ← qa p ε qd p ,	⊗
!fcnter&path  ∂(n)⊗⊗ter p ← [qa p = final] ,	⊗
!fcnsuccessors&path  ∂(n)⊗⊗successors p ← mapcar[λx: x . p, qd assoc[qa p, graph]]⊗.
.end

The node we are proposing to visit next loses if it is already in
the path, as that means we have been here before.  The successors to a position
are all of those positions immediately reachable from the current node.
In our list notation for a graph the immediately reachable nodes are those
on the list associated with the current node in ⊗graph.  A position is
terminal if the current node is the desired goal ⊗final.  

	⊗search is used when we want to search a tree of possibilities
for a solution to a problem.
Naturally we can do other things with tree search recursion than just
search.  For example we may want to find all solutions
to a problem.  This can be done with a function ⊗allsol that uses
the same ⊗lose, ⊗ter, and ⊗successors functions as does ⊗search. 
The simplest way to write ⊗allsol is

!fcnallsol&  ⊗⊗⊗allsol p ← qif lose p qthen qNIL qelse qif ter p
qthen <p> qelse mapapp[allsol, successors p]⊗,

where

!fcnmapapp&  ⊗⊗⊗mapapp[fn, u] ← qif qn u qthen qNIL qelse fn[qa u] * mappap[fn, qd u]⊗.

This form of the function is somewhat inefficient because of all the
⊗⊗append⊗ing.  A more efficient form uses an auxiliary function as follows: 
.begin nofill turnon "∂"
.n←16

∂(n)		 ⊗⊗allsol p ← allsola[p, qNIL]⊗

.group
∂(n)	⊗⊗allsola[p, found] ← ⊗
∂(n+4)	⊗⊗qif lose p qthen found⊗
!fcnallsol&a ∂(n+4)	⊗⊗qelse qif ter p qthen p . found⊗
∂(n+4)	⊗⊗qelse allsolb[successors p, found]⊗,
.apart

∂(n)	⊗⊗allsolb[u, found] ← qif qn u qthen found qelse allsolb[qd u, allsola[qa u, found]]⊗.
.end

The recursive program structure that arises here is common when a list
is to be formed by recurring through a list structure.

	We will give further applications of and variations on this form
of tree search recursion in Chapter {SECTION SEARCH}.
.ss(soln, Solving a LISP programming problem.)

	In this section we present a programming problem
that is somewhat more complex than the examples of earlier sections
and work out the solution in detail, the purpose being to help you
get started thinking recursively and to show how a typical problem
might be approached.   After describing the function we wish to compute,
we will write programs for two simpler but related functions in order to better
understand various aspects of the control structure and information
flow needed in the main computation.  This is a useful technique in
problem solving in general, the trick of course is to find a simplification
which produces a problem that you can solve and whose solution is
useful in solving the original problem.   Having written programs for 
these simpler functions, we then use the insight gained to 
to solve the main problem.

	The problem has to do with "lists of lists" or L-lists.  An L-list
is either the empty list, qNIL, or and atom ⊗⊗cons⊗ed onto the front of
an L-list, or an L-list ⊗⊗cons⊗ed onto the front of an L-list.   Thus
$$(A_(A_B)_C)$ is and L-list, but $$(A_(B_._C)_D)$ is not.   Although
this class of S-expressions is less general than the usual LISP notion
of list, it is more uniform.  The
computation of a function on L-lists may use the value of the function
on the ⊗car of the L-list (when it is non-atomic) as well as on the 
⊗cdr as both are again L-lists.

	The function ⊗allsubsub returns a list of all occurrences of an 
L-list ⊗u as a sublist or as a sublist of a sublist of an L-list ⊗v .  
For example $$(A A)$ occurs three times as a subsublist of $$(A A A B A A)$
and $$(A)$ occurs 4 times in $$(A (B (A A)) (C (((A)))))$.

	Suppose we restrict the function to lists of atoms.
Thus we wish to compute the function ⊗allsub that returns a list of all 
occurrences of a list of atoms ⊗u as a sublist of another list of atoms ⊗v.  
The first thing to do is decide on the representation of an
occurrence of one list as a sublist of another list.  In the case of 
lists of atoms, a fairly natural solution is to represent an occurrence of a
particular sublist as the number ⊗n corresponding to position in the list 
of the beginning of that occurrence.  Thus  

⊗⊗⊗allsub[$$(A A),(A A A B A A)$] = $$(1 2 5)$.⊗

	To compute ⊗allsub[u,v], if ⊗v is qNIL then the answer is qNIL.
Otherwise, imagine that we know the answer for ⊗⊗qd v⊗.
Then there are two possiblities.
Either ⊗u "matches" ⊗v (⊗v may be longer than ⊗u, but up to the end of ⊗u 
the elements of ⊗v and ⊗u are the same), or not.  If not, the answer is
just the result for ⊗⊗qd v⊗ otherwise we add the current
position to the result for ⊗⊗qd v⊗.  This analysis
suggests that we will need an additional argument to keep track of
the current position.  Thus we define a function ⊗⊗allsub1[u,v,p]⊗ 
where the argument ⊗p is intended to correspond to the position of
the argument ⊗v in the initial list.  If ⊗v is qNIL then the
result is qNIL.  Otherwise suppose we know the value of ⊗⊗allsub1[u,qd v,p+1]⊗
then we either add ⊗p onto that value or return it unchanged according to
whether or not ⊗u matches ⊗v.  Assuming we have a suitable definition of 
⊗match, the above analysis leads to the following definitions:
.begin nofill  turnon "∂"
.n←12; m←16

.group
∂(n)⊗⊗allsub[u, v] ← allsub1[u, v, 1]⊗
!fcnallsub& 
∂(n)⊗⊗allsub1[u, v, p] ← ⊗
∂(m)⊗⊗qif qn v qthen qNIL⊗
∂(m)⊗⊗qelse qif match[u, v] qthen p . allsub1[u, qd v, $1 + p]⊗
∂(m)⊗⊗qelse allsub1[u, qd v, $1 + p]⊗.
.apart
.end
	It remains for us to write the definition of
⊗match[u,v] which determines whether or not ⊗u matches the beginning of ⊗v.  
This is easy.  If ⊗u is qNIL then we have gotten to the end of ⊗u 
with out finding a mismatch so we return qT.   If ⊗v is qNIL (and ⊗u is not)
then we return qNIL and ⊗u does not match the beginning of ⊗v.  
Otherwise the result is qT only if ⊗⊗qa u_=_qa v⊗ and the ⊗⊗cdr⊗s of ⊗u and ⊗v 
match.  Thus

!fcnmatch& ⊗⊗⊗match[u, v] ← 
 qif qn u qthen qT qelse qif qn v qthen qNIL qelse qa u = qa v ∧ match[qd u, qd v]⊗.

The internal forms of the above definitions are
.begin nofill select 6

.group
	(DEFUN ALLSUB (U V) (ALLSUB1 U V 1)) 

	(DEFUN ALLSUB1 (U V P) 
	       (COND ((NULL V) NIL)
		     ((MATCH U V) (CONS P (ALLSUB1 U (CDR V) (ADD1 P))))
		     (T (ALLSUB1 U (CDR V) (ADD1 P))))) 
.apart

.group
	(DEFUN MATCH (U V) 
	       (COND ((NULL U) T)
		     ((NULL V) NIL)
		     (T (AND (EQUAL (CAR U) (CAR V))
			     (MATCH (CDR U) (CDR V)))))) 
.apart
.end

	Now we return to the ⊗allsubsub problem. 
As with the simpler case, we must first decide how to represent an occurrence 
of an L-list as a subsublist of an L-list.  Again we need only represent the
position where the list match begins.  Consider an arbitrary point, ⊗p,  in an
L-list.  Either it is an element of the list, or is contained in one of the
elements of the list.  In the first case the position ⊗n of the element is
sufficient, in the second case we need the position ⊗n of the element together
with the position of the point ⊗p relative to that element.
Thus in the first case we take the list containing only the number ⊗n and
in the second case we add ⊗n onto the list representing the position of ⊗p 
in the ⊗⊗n⊗th element of the list.  Using this representation we have

⊗⊗⊗allsubsub[$$(A),(A (B (A A)) (C (((A)))))$] = $$((1) (2 2 1) (2 2 2) (3 2 1 1 1))$⊗ .

	To construct the desired list of positions we check for a match of ⊗u 
at each position and add matching positions to the result.   (Actually 
we will see that some positions can be ruled out with out explicitly checking 
for a match.)  In particular, we will need to pass around sufficient information
to be able to construct a representation of the current position whenever a match
is found.  Let us consider the simpler problem of computing ⊗allpos[v], a list
of all the positions in ⊗v.  A program for this  can easily be modified 
to list only those positions satisfying the "match" condition.
A definition of ⊗allpos can be obtained by recalling the discussion about of how
a position is to be represented.  Namely if ⊗n is the position of ⊗v 
in the list of which ⊗v is a tail then
(i) if ⊗v is qNIL then there are no positions and the answer is qNIL,  
(ii) ⊗⊗qa v⊗ is an atom then add ⊗<n> to the list of positions in ⊗⊗qd v⊗
passing ⊗⊗n+1⊗ as the current position number
(iii) otherwise compute the list of positions in ⊗⊗qa v⊗ (relative to ⊗⊗qa v⊗),
tack ⊗n onto the front of each position, append this onto the list of
positions in ⊗⊗qd v⊗ (again passing ⊗n+1) and finally add the current
position, ⊗<n>, to the result.   Thus we have

.begin nofill turnon "∂"
.n←12;  m←16;

.group
∂(n)⊗⊗allpos v ← allpos1[v, 1]⊗
!fcnallpos& 
∂(n)⊗⊗allpos1[v, n] ← ⊗
∂(m)⊗⊗qif qn v qthen qNIL⊗
∂(m)⊗⊗qelse qif qat qa v qthen <n> . allpos1[qd v, $1 + n]⊗
∂(m)⊗⊗qelse <n> . [tack[n, allpos qa v] * allpos1[qd v, $1 + n]]⊗
.apart

!fcntack& ∂(n)⊗⊗tack[n, w] ← qif qn w qthen qNIL qelse [n . qa w] . tack[n, qd w]⊗
.end

Now we modify to ⊗allpos and ⊗allpos1 to carry around the parameter ⊗u 
and rule out those positions that don't match.  In particular
we only add ⊗<n> to the list if ⊗match[u,v] is satisfied, and in
this case we don't look for a match in ⊗⊗qa v⊗ as the top level
match makes this impossible (recall our lists are finite tree-like structures).
So we arrive at the following:
.begin nofill turnon "∂"
.n←12;  m←16;

.group
∂(n)⊗⊗allsubsub[u, v] ← allsubsub1[u, v, 1]⊗
!fcnallsubsub& 
∂(n)⊗⊗allsubsub1[u, v, n] ← ⊗
∂(m)⊗⊗qif qn v qthen qNIL⊗
∂(m)⊗⊗qelse qif match[u, v] qthen <n> . allsubsub1[u, qd v, $1 + n]⊗
∂(m)⊗⊗qelse qif qat qa v qthen allsubsub1[u, qd v, $1 + n]⊗
∂(m)⊗⊗qelse tack[n, allsubsub[u, qa v]] * allsubsub1[u, qd v, $1 + n]⊗
.apart
.end

An alternate solution for the ⊗allpos and the ⊗allsubsub problems
is to pass along a complete representation of the current position.  
When we pass it in the ⊗⊗qd v⊗ direction we need to add 1 to the
last element and when we pass it in the ⊗⊗qa v⊗ direction we need to
add a 1 to the end of the list.  Since all of the action is at the
end of the list it is easier to pass along the reverse of the position
list and re-reverse it when returning the position as an answer.  
Thus we get the following definitions 
.begin nofill turnon "∂"
.n←12;  m←16;

.group
∂(n)⊗⊗allpos v ← allpos1[v, $$(1)$]⊗
!fcnallpos&1 
∂(n)⊗⊗allpos1[v, p] ← ⊗
∂(m)⊗⊗qif qn v qthen qNIL⊗
∂(m)⊗⊗qelse qif qat qa v qthen reverse p . allpos1[qd v, [$1 + qa p] . qd p]⊗
∂(m)⊗⊗qelse reverse p . [allpos1[qa v, 1 . p]] * allpos1[qd v, [$1 + qa p] . qd p]]⊗
.apart

.group
∂(n)⊗⊗allsubsub[u, v] ← allsubsub1[u, v, $$(1)$]⊗
!fcnallsubsub&1 
∂(n)⊗⊗allsubsub1[u, v, p] ← ⊗
∂(m)⊗⊗qif qn v qthen qNIL⊗
∂(m)⊗⊗qelse qif match[u, v] qthen reverse p . allsubsub1[u, qd v, [$1 + qa p] . qd p]⊗
∂(m)⊗⊗qelse qif qat qa v qthen allsubsub1[u, qd v, [$1 + qa p] . qd p]⊗
∂(m)⊗⊗qelse allsubsub1[u, qa v, $1 . p]] * allsubsub1[u, qd v, [$1 + qa p] . qd p]⊗
.apart
.end

Notice that in the first solution, the construction of the position representation
was taken care of somewhat automatically by the recursive structure of the program,
while in the second case we had to worry about the details of constructing
the position representations.

In both cases the compution works by passing information both down and across
the list structure and getting results back.  What is passed on and the 
interpretation of the result returned depends on the direction. 
In this example there is no exchange of information between the subcomputations.
In a more complicted situation this might also be necessary.

.next page
.ss(writinex, Lots of LISP functions to program.)

	The following are descriptions of functions on lists and S-expressions.
You should write LISP programs to compute these functions.  A description
of the form  "⊗foo[x] is true if and only_if_..."  means your program should
return qT in the case that ⊗foo[x] is true and qNIL otherwise.
Write your solutions out in external form, if you like, then
convert them to internal form and try them out in whatever LISP system
you have access to.   You should convince yourself by some informal
process of reasoning that your solutions are indeed correct.  You
will be asked to prove various facts about your programs after you
have studied Chapter {SECTION PROVIN}.  This should encourage you to
write clean, understandable programs and document them carefully
so you will remember why you thought they were correct to begin with
and what tricks you may have employed.


	The problems are classified according to the intended interpretation
of the lists or S-expressions.  The classes include lists, S-expressions,
arithmetic expressions, polynomials, (finite) sets, permutations, trees, and graphs.
Each group begins with some simple problems (with one line solutions)
to get you going.  For the more complicated functions, you will find
that defining auxiliary functions is useful.  Towards the end the programs
may require a fair amount of thinking to get things organized correctly,
but none of the problems require really lengthy programs.
Pay attention to getting the trivial cases (e. g. when some of the arguments
are qNIL or atomic or otherwise to be considered basic) correct.  It is 
in general important to understand the trivial cases in the computation
of a function.

	The observant reader will no doubt notice that some of these
functions are defined in later chapters.  Thus you will have some
cases where you can compare your solution to those given.   (Pointers
to these definitions can be found in the function index.)

.begin "exerci"
.indent 0,3
.cb Lists
.item ← 0

#. ⊗samelength[u,v] tests whether the lists ⊗u and ⊗v have the same length.
.begin nofill

⊗⊗⊗samelength[$$(A B C), (D E F)$] = qT⊗
⊗⊗⊗samelength[$$(A B C), (A C)$] = qNIL⊗
.end
    Do not use any operations or test on numbers to write your program.


#. ⊗prup[u,v] is the list formed by pairing the corresponding elements
of the lists ⊗u and ⊗v.  Thus

⊗⊗⊗prup[$$(X Y Z), (1 A (FOO BAR))$] = $$((X . 1) (Y . A) (Z FOO BAR))$⊗.

.if false then begin "assoc-inverse"
#. ⊗assoc-inverse[x,a] is a list of expressions associated with ⊗x in 
in the list of pairs (association-list) ⊗a.  Thus 
.begin nofill

⊗⊗⊗assoc-inverse[$$(OR A B), ((P AND A C) (Q OR A B) (R IMPLIES C B) (S OR A B))$]
= $$(Q S)$⊗
⊗⊗⊗assoc-inverse[$$1, ((X . 2) (Y . 0))$] = qNIL  ⊗.
.end
.end  "assoc-inverse"

#. ⊗istail[u,v] is true if and only if the list ⊗u is a tail of ⊗v.  That is
when ⊗⊗cdr⊗ing through ⊗v you will eventually get to ⊗u.  

#. ⊗commontail[u,v] is the longest common sublist of
⊗u and ⊗v ending with the ends of the lists.  Thus

⊗⊗⊗commontail[$$(A B C D E),(A C D E)$] = $$(C D E)$⊗.

#.  ⊗upto[u,v] when ⊗u is a tail of ⊗v, is the list of elements of ⊗v 
upto the point where ⊗u begins.  Thus

⊗⊗⊗upto[$$(C D E),(A B C D E)$] = $$(A B)$⊗.

. if false then begin "nth"
#. ⊗nth[u,n] is the ⊗⊗n⊗th element of the list ⊗u.  

#. ⊗nthpos[u,n] is the sublist of ⊗u beginning with the ⊗⊗n⊗th element.

#. ⊗least[u] is the least integer in the list ⊗u of integers.
.end "nth"

#. ⊗mapapp[f,u] appends together the lists obtained by applying ⊗f to successive
elements of ⊗u.  

#. ⊗mapchoose[p,u] forms a list of those elements of ⊗u satisfying ⊗p.  

#. ⊗partition[u,n] is the list of partitions of the list ⊗u into
⊗n sublists ⊗u1, ... ⊗un such that ⊗⊗u1*[u2*...*un]=u⊗.  
If ⊗n is greater than the length of ⊗u then your program should return
an error message of some kind.
Thus 

⊗⊗⊗partition[$$(A B C),2$]=$$((A) (B C))((A B) (C)))$⊗

   Write a program ⊗testpart to test the result returned by ⊗partition.  
For each partition, ⊗testpart should append together the lists ⊗ui 
and check that the result is ⊗u.  


.cb S-expressions

#. ⊗mirror[x] returns the mirror image of an S-expression ⊗x.  
Thus 

⊗⊗⊗mirror[$$((A.B).(C.D))$]=$$((D.C).(B.A))$⊗.

#. ⊗occur[x,y] is true if and only if the atom ⊗x occurs in the S-expression 
⊗y.  For example

⊗⊗⊗occur[$B, $$((A.B).C)$] = qT⊗.

#. ⊗multiplicity[x,y] is the number of times the atom ⊗x occurs in 
the S-expression ⊗y.  

.if false then begin "atoms"
#. ⊗set-of-atoms[x] is a list without duplications of the atoms occurring in 
the S-expression ⊗x. 

#. ⊗bag-of-atoms[x] is a list of all atoms that occur in the
S-expression ⊗x paired with their multiplicities.
.end "atoms"

        A path in an S-expression ⊗x is a list of $$A$'s and $$D$'s such that you can
apply a succession of qqa's or qqd's to ⊗x (according to whether the next list
element is $A or $$D$)  without trying to apply qqa or qqd to an atom.  We say
that the resulting subexpression is at the end of the path or that the path leads
to that subexpression.  Thus 
$$(A_D)$ is a path in $$((X_._(Y_._Z))_._F)$  but $$(D_A)$ is not.
Also $$(Y_._Z)$ is at the end of the path $$(A_D)$ in $$((X_._(Y_._Z))_._F)$.

#. ⊗ispath[p,x] is true if and only if ⊗p is a path in ⊗x.  

#. ⊗depth[x] is the length of the longest path leading to an atom in the 
S-expression ⊗x.  

⊗⊗⊗depth[$$(((A . B) . C) . D$] = $$3$⊗.

        We say that an S-expression is balanced if it is an atom or if
⊗⊗depth[qa x]⊗ and ⊗⊗depth[qd x]⊗ differ by at most 1
and qa ⊗x and qd ⊗x are both balanced.  

#. ⊗balanced[x] is true if and only if the S-expression ⊗x is balanced.

#.  ⊗balance x is balanced and has the same fringe as x

#. ⊗get[y,p] is the subexpression at the end of the path ⊗p in the
S-expression ⊗y.  Thus

⊗⊗⊗get[$$(A ((B) C) (B)), (D A A)$] = $$(B)$⊗.

#. ⊗point[x,y] is the path in the S-expression ⊗y leading to the left-most 
occurrence of the S-expression ⊗x in the S-expression ⊗y. Thus

⊗⊗⊗point[$$(B), (A ((B) C) (B))$] = $$(D A A)$⊗.

#. ⊗allpoint[x,y] is a list of all paths ⊗p such that ⊗⊗get[y,p]_=_x⊗.  Thus

⊗⊗⊗allpoint[$$(B), (A ((B) C) (B))$] = $$((D A A) (D D A))$⊗.

#. ⊗⊗commons x⊗ is a list of the subexpressions of the S-expression
⊗x that occur more than once in ⊗x, each followed by a list of the points 
(paths leading to the points) where it occurs. 

.if false then begin "sublis"
#. Let ⊗a be an association list pairing variables (atoms satisfying ⊗⊗isvar⊗)
their associated values (arbitrary S-expressions).  ⊗sublis[x,a] 
replaces every occurrence of a variable in the S-expressions ⊗x with
its associated value in ⊗a.  This is done by "simultaneous" rather that
"sequential" substitution so that if the value associated with a variable
happens to have a variable in it, that occurrence of the variable will 
remain in the result.

#. Let ⊗p be an S-expression with certain of the atoms
occurring ⊗p regarded as variables, e.g. those atoms satisfying ⊗isvar 
as in the previous problem.  For any S-expression ⊗x, if
there are substitutions for the variables in ⊗p  that
make ⊗p and ⊗x the same expression, then ⊗match[x,p] is a list of pairs
such that

⊗⊗⊗sublis[p,match[x,p]] = x⊗

    Otherwise, ⊗match[x,p] = $NO.  For example,

⊗⊗⊗match[$$(PLUS(TIMES X Y) Z), (PLUS &X &Y)$] = $$((&X TIMES X Y) (&Y . Z))$⊗

    where only the atoms $&X and $&Y are regarded as variables.
.end "sublis"

.cb Symbolic arithmetic and algebra

#. Let a polynomial in ⊗x be represented by a list of its coefficients
in order of ascending powers of ⊗x.  Thus ⊗⊗x%53%*+x+5⊗ is represented
by $$(5 1 0 1)$.  
.begin nofill indent 8,8

	##. ⊗sum[u,v]  is the sum
	##. ⊗prod[u,v]  is the product 
	##. ⊗quot[u,v] is the quotient 
	##. ⊗rem[u,v] is the remainder 
.end

    of the polynomials ⊗u and ⊗v in the same notation.


#.  Consider arithmetic expressions as represented in this chapter.
Namely an expression is 
.begin nofill indent 8,8

	(i) a number (satisfies ⊗numberp), 
	(ii) a variable (not a number and satisfies qqat),
	(iii) a sum : $PLUS . < list of expressions > or
	(iv) a product : $TIMES . < list of expressions >.
.end
    (For simplicity, assume the sum and product lists always have at least 2 elements.)

	The function ⊗sop converts such expressions into sum of products
form, eg. the resulting expression is either a monomial 
or a sum of monomial terms which has the form $$PLUS$_._<list_of_monomials>.
A monomial is either a number, a variable, or a product of the 
form $$TIMES$_._< list of numbers or variables >.

	Try your simplifier on expressions returned by ⊗diff.  


.cb Sets

#. Lists can be thought of as representing finite sets using the
the program ⊗⊗member[x, u]⊗ defined earlier, to compute the membership
relation.   Write programs to compute the functions
union, ⊗⊗u_∪_v⊗, intersection, ⊗⊗u_∩_v⊗, and the set difference, ⊗⊗u-v⊗,
for lists ⊗u and ⊗v viewed as representing sets.  For example:
.begin nofill

⊗⊗⊗$$(A B C) ∪ (B C D) = (A B C D)$,⊗
⊗⊗⊗$$(A B C) ∩ (B C D) = (B C)$,    ⊗
and
⊗⊗⊗$$(A B C) - (B C D) = (A)$.      ⊗
.end

[Remark: 
There are a couple of possible conventions for representing finite sets as lists.  
One is to require S-expressions representing elements of a set to occur in the 
representing list exactly once.   The other is to allow multiple occurrences
of an S-expression representing an element of the set.  You should decide
which convention you wish to adopt, and make sure your programs are consistent
with that convention.]

#. Suppose ⊗x takes numbers as values and ⊗u takes as
values lists of numbers in ascending order, e.g. $$(2 4 7)$.  Write a
function ⊗⊗insert[x, u]⊗ whose value is obtained from that of ⊗u by
putting ⊗x in ⊗u in its proper place.   Thus
.begin nofill

⊗⊗⊗insert[$3, $$(2 4)$] = $$(2 3 4)$⊗, 
and 
⊗⊗⊗insert[$3, $$(2 3)$] = $$(2 3 3)$⊗.
.end

#. Write functions giving the union, intersection, and set
difference of ordered lists; the result is wanted as an ordered list.

	Note that computing these functions of unordered lists takes
a number of comparisons proportional to the square of the number of
elements of a typical list, while for ordered lists, the number of
comparisons is proportional to the number of elements.

#. Using ⊗insert, write a function ⊗sort that transforms an
unordered list into an ordered list.

#. Write a function ⊗goodsort that sorts a list using a
number of comparisons proportional to ⊗⊗n_log_n⊗, where ⊗n is the
length of the list to be sorted.


.cb Permutations

#.  ⊗rcycle[u]  is obtained from the list ⊗u by moving the
last element to the first position.  Thus

⊗⊗⊗rcycle[$$(A B C D)$] = $$(D A B C)$⊗.

#. ⊗lcycle[u]  is obtained from the list ⊗u by moving the
first element to the last position.  Thus

⊗⊗⊗lcycle[$$(A B C D)$] = $$(B C D A)$⊗. 


        We can think of a permutation on ⊗n objects as a function which maps
a list $$(l1 l2 ... lN)$ of ⊗n distinct elements 
to a list containing the same elements in  a
different order.  Thus  $$(3_4_1_2)$ is a permutation of $$(1_2_3_4)$ and
$$(FOO_BAR_BAZ)$ is a permutation of $$(BAR_BAZ_FOO)$.
The permutation itself can be represented as a list in several ways.
We describe two possible representations of a permutation ⊗pi.  

	$REP1:  ⊗pi is represented as a list of numbers $$(j1_j2_..._jN)$ 
which is itself a permutation of the list $$(1_2_..._N)$ and the result of 
applying such a permutation to a list ⊗u of length ⊗n is the list ⊗u' 
where the ⊗⊗k⊗th element of ⊗u' is the ⊗⊗jk⊗th element of ⊗u.  
Thus the permutation $$(2 3 4 1)$ applied to the list $$(A B C D)$
is the list $$(B C D A)$.  $$(1 2 3 4)$ is the identity permutation.

	$REP2:  ⊗pi is represented as a list of disjoint cycles, 
where a cycle is a a list of length at most ⊗n of numbers between 1 and ⊗n 
(with no two elements the same).  The permutation represented by such a
list of cycles is the permutation that results from applying each of the cycles.
(The order of application doesn't matter since the cycles are disjoint.)
The result of applying a cycle $$(j1_j2_..._jk)$ 
to a list ⊗u of lenght ⊗n is the list ⊗u' where the element in position
⊗jm in ⊗u' is the element in position ⊗jm-1 in ⊗u for ⊗1≤m≤k 
(taking ⊗j0 to be ⊗jk).  Elements in positions not mentioned 
in the cycle are unchanged.
Thus the cycle  $$(1_4_2)$ applied to $$(A_B_C_D)$ gives $$(B_D_C_A)$.
The empty list of cycles is the identity permutation in this representation.

#. ⊗isperm1[pi,n] (⊗⊗isperm2[pi,n]⊗) is true just if the list ⊗pi represents 
a permutation on ⊗n objects according to $REP1 ($$REP2$).

#. ⊗sameperm2[pi1,pi2] is true if and only if ⊗pi1 and ⊗pi2 represent the same
permutation.  (Note that the representation by $REP2 is not unique
while in $REP1 it is.)

#. ⊗rho12[pi] maps a list ⊗pi representing a permutation according to
$REP1 to a list representing the same permutation according to $REP2.  
⊗rho21[u] is the inverse map.  

#. ⊗compose1[pi1,pi2] represents the permutation that results if ⊗pi2 is
applied followed by ⊗pi1, all represented according to $REP1.  
⊗compose2[u,v] does the same but using $REP2.  

#. ⊗invert1[pi] (⊗⊗invert2[pi]⊗) is the inverse to the permutation ⊗pi, 
in $REP1 ($$REP2$).  Thus ⊗⊗compose1[invert1[pi],pi]⊗ is the identitiy
permutation.

        Note that one way to solve the above problems would be to write the
programs for one representation and use the transformations ⊗rho12 and ⊗rho21 
to obtain those for the other representation.  However part of the
purpose of the exercise is to see how the different representations behave and
this solution would defeat that purpose.

.cb Trees

	 Consider a tree structure represented as a list in the following
way.  A leaf is any list of the form $$(LEAF e)$ where $e is any
S-expression.  A tree is either a leaf, or a list of trees.

#.  ⊗leaves t is a list of all the leaves in the tree ⊗t, in the same
order as they appear in  the tree.  (Compare to ⊗fringe for S-expressions.)

#.  Let ⊗leafval be an evaluation function on leaves.  (Assume ⊗leafval
returns integers.)
⊗⊗bestleaf t⊗ is a leaf of ⊗t having a maximal value according ⊗leafval.
That is no other leaf of ⊗t has a better value.

#. ⊗⊗bestleaf1 t⊗ is a leaf of ⊗t of maximal value and among those of
the same value, ⊗⊗bestleaf1 t⊗ has least depth (is closest to the root).

.cb graphs

	Let ⊗g be a directed graph represented as a list of lists as described
earlier in this chapter.

#. ⊗isnext[u,v,g] is true if and only if ⊗g contains an edge from ⊗u to ⊗v.  

#. ⊗successors[u,g] is the list of vertices, ⊗v, in ⊗g such that ⊗isnext[u,v,g].  

#. ⊗predecessors[u,g] is the list of vertices ⊗v, in ⊗g such that ⊗isnext[v,u,g].  

#. ⊗undir[g] is true if and only if ⊗g is undirected.  That is, if for every
edge from ⊗u to ⊗v in ⊗g there is also and edge from ⊗v to ⊗u.  

#.  ⊗mkundir[g] is the graph ⊗g1 with the same vertices as ⊗g, and  such that
there is an edge from ⊗u to ⊗v in ⊗g1 if and only if ⊗g has either an edge from
⊗v to ⊗u or and edge from ⊗u to ⊗v.  

#.  If ⊗g is undirected then
⊗deleteα_vertex[v,g]  returns a graph ⊗g1 with vertices those of
⊗g omitting ⊗v, and edges the same as ⊗g omitting those connecting ⊗v to 
another vertex. 

#. If ⊗g is undirected then
⊗complement[g]  returns a graph ⊗g1 with vertices the same as ⊗g, but
vertices ⊗v and ⊗w are joined by an edge in ⊗g1 if and only if they are not
joined by an edge in ⊗g.  

#. For any graph ⊗g, ⊗reachable[u,v,g] is true if and only if there is a
sequence of vertices ⊗u1, ⊗u2, ... ,⊗un  in ⊗g with ⊗u = ⊗u1, ⊗v = ⊗un and
⊗isnext[ui,ui+1,g] for ⊗1≤i≤n-1.  

#. For any graph ⊗g, 
⊗conn[g] is true if and only if the directed graph ⊗g is connected in the sense
that every vertex is reachable from every other vertex.  

NB:  Graphs in general have cycles, so when you are recurring through a graph
you need to keep track of where you have been in order to avoid a forever
looping program.


.end "exerci"